/*输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
    	if(pHead == nullptr)
    		return nullptr;
    	RandomListNode *p = pHead;
        while(p)
        {
        	RandomListNode *cp = new RandomListNode(p->label);
        	cp->next = p->next;
        	p->next = cp;
        	p = p->next->next;
        }
        RandomListNode *cp = pHead->next;
        p = pHead;
        while(cp)
        {
        	if(p->random != nullptr)
        		cp->random = p->random->next;
        	p=p->next->next;
        	if(p == nullptr)
        		break;
        	cp=cp->next->next;
        }
        //split
        RandomListNode *pOrigin = pHead;
        pHead = pHead->next;
        cp = pHead;
        p = pHead->next;
        while(p)
        {
        	pOrigin->next = p;
        	pOrigin = pOrigin->next;
        	cp->next = p->next;
        	cp = cp->next;
        	p = cp->next;
        }
        pOrigin->next = p;
        return pHead;
    }
};